package mashibing.class9;

import pojo.ListNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 链表拷贝(value next random)
 *
 * @author yujiafan
 * @version 1.0.0
 * @create 2023-05-15
 */
public class Class9_7_CopyNodeWithRandom {

    public static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    // 使用map容器，key:老节点 -> value:新节点
    public static Node CopyNodeWithRandom1(Node head){
        if(head == null){
            return null;
        }
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null){
            map.put(cur,new Node(cur.val));
            cur = cur.next;
        }
        // 拷贝新节点
        cur = head;
        while (cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }

    // 1->1'->2->2'->null
    public static Node CopyNodeWithRandom2(Node head){
        if(head == null){
            return null;
        }
        // 链表插入克隆节点
        Node cur = head;
        Node next;
        while (cur != null){
            next = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = next;
            cur = next;
        }
        // 新节点编辑random值
        cur = head;
        Node copyCur;
        while (cur != null){
            next = cur.next.next;
            copyCur = cur.next;
            copyCur.random = cur.random == null ? null : cur.random.next;
            cur = next;
        }
        // 分割链表split
        cur = head;
        Node ans = cur.next;
        while (cur != null){
            next = cur.next.next;
            copyCur = cur.next;
            copyCur.next = next == null ? null : next.next;
            cur.next = next;
            cur = next;
        }
        return ans;
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        node1.next = node2;
        node1.random = node3;
        node2.next = node3;
        node2.random = null;
        node3.random = node1;
        printLinkedList(node1);
        Node copy1 = CopyNodeWithRandom1(node1);
        printLinkedList(copy1);
        Node copy2 = CopyNodeWithRandom2(node1);
        printLinkedList(copy2);
        // 看一下链表结构有无恢复
        printLinkedList(node1);
    }

    public static void printLinkedList(Node node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
        System.out.println();
    }
}
